package com.base.string;

import java.util.*;

/**
 * TODO
 *
 * @author leon
 * @date 2021年10月27日 22:32
 */
public class RemoveInvalidParentheses {

    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new LinkedList<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(s);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size>0){
                String ss = queue.remove();
                size--;
                if (isValid(ss)){
                    res.add(ss);
                }else {
                    StringBuilder sb = new StringBuilder(ss);
                    for (int i = 0; i < sb.length(); i++) {
                        if (sb.charAt(i)!='('||sb.charAt(i)!=')'){
                            continue;
                        }
                        String s1 = String.valueOf(sb.deleteCharAt(i));
                        queue.add(s1);
                    }
                }
            }

            if (res.size()>0){
                return res;
            }
        }
        return res;
    }

    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }


}
